/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <stack>
#include <queue>
using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
	treeHeight = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	// pf is the pagefile used to store the actual B+tree in disk
	RC temprc;
	temprc = pf.open(indexname, mode);
    if (temprc != 0)
	{
		return RC_FILE_OPEN_FAILED;
	}
	if (mode == 'w') // file was created in write mode
	{
		rw_mode = 'w';
	}
	else // file was created in read mode
	{
		rw_mode = 'r';
	}
	
	char buffer[PageFile::PAGE_SIZE];
	if (pf.read(0, buffer) != 0) // buffer will now be read from pf, pid 0 (root)
	{
		return RC_FILE_OPEN_FAILED;
	}
	char *tempbuffer = buffer;
	memcpy(&rootPid, tempbuffer, sizeof(PageId));
	memcpy(&treeHeight, tempbuffer+sizeof(PageId), sizeof(int));
	return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	if (rw_mode == 'w') // have to write something to disk
	{
		char buffer[PageFile::PAGE_SIZE];
		char *tempbuffer = buffer;
		memcpy(tempbuffer, &rootPid, sizeof(PageId));
		memcpy(tempbuffer+sizeof(PageId), &treeHeight, sizeof(int));
		if (pf.write(0, buffer) != 0)
		{
			return RC_FILE_WRITE_FAILED;
		}
	}
    return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
    RC status;
    int currentHeight = 1;
    BTLeafNode leaf;
    PageId currentPid = rootPid;
    stack<PageId> parents;
    bool newroot = true;

    
    leaf.initialize(); // initialize leaf, so it contains key -1, RecordId.pid -1, RecordId.sid -1
    
//    printf("Insert %d \n", key);
    
    // special case: tree is empty
    if(treeHeight == 0){
        status = leaf.insert(key, rid);
        if(status != 0)
            return status;
        rootPid = 1; // since 0 is metadata        
        status = leaf.write(rootPid, pf);
       
        if(status != 0)
            return status;
        treeHeight = 1;
    }
    else{
        // go through the middle nodes of the tree
        while(currentHeight < treeHeight){
            parents.push(currentPid);
            BTNonLeafNode nonleaf;
        
            // read data into buffer
            status = nonleaf.read(currentPid, pf);
            if(status != 0)
                 return status;
        
            // retrieve the childnode
            status = nonleaf.locateChildPtr(key, currentPid);
            if(status !=0)
                return status;
            
            currentHeight ++;        
        }
        
        // now the currentPid should be pointing at leaf node    
        status = leaf.read(currentPid, pf); // read leaf data into buffer
        if(status != 0)
            return status;
            
        // insert into leaf node
        if(leaf.insert(key, rid) == 0){ // successfully inserted, write to file
            status = leaf.write(currentPid, pf);            
            newroot = false;
        }
    
        else{ // leaf overflow
            BTLeafNode leafSibling;
            leafSibling.initialize();
            PageId siblingPid = pf.endPid();
            int siblingKey;
        
            status = leaf.insertAndSplit(key, rid, leafSibling, siblingKey); // insert and split        
            if(status != 0)
                return status;
        
            // update sibling next node
            leafSibling.setNextNodePtr(leaf.getNextNodePtr());
            leaf.setNextNodePtr(siblingPid);
        
            //write to file
            leaf.write(currentPid, pf);
            leafSibling.write(siblingPid, pf);
        
            // insert to parent node
            int keyToInsert = siblingKey;
            PageId pidToInsert = siblingPid;
            PageId leftPid = currentPid;
                        
            while((int)parents.size() > 0){
                BTNonLeafNode parentNode;
                PageId parentPid = (PageId) parents.top();
                parents.pop();
                
                parentNode.initialize(); //initialize parent node
                status = parentNode.read(parentPid, pf); // load the parent node
                if(status !=0)
                    return status;
            
                if(parentNode.insert(keyToInsert, pidToInsert) == 0){ // insert succesffully, write to file
                    parentNode.write(parentPid, pf);
                    newroot = false;
                    break;  // insert succesffully
                }
                else{  // non-leaf overflow
                    BTNonLeafNode nonleafSibling;
                    PageId nonleafSiblingPid = pf.endPid();
                    int sibKey;
                    nonleafSibling.initialize();
                    
                    status = parentNode.insertAndSplit(keyToInsert, pidToInsert, nonleafSibling, sibKey);
                    if(status !=0)
                        return status;
                
                    //write to file
                    parentNode.write(parentPid, pf);
                    nonleafSibling.write(nonleafSiblingPid, pf);                
                
                    keyToInsert = sibKey;
                    pidToInsert = nonleafSiblingPid;
                    leftPid = parentPid;
                }            
            }
        
            // insert the new node to root
            if(newroot == true){
                BTNonLeafNode rootNode;
                rootNode.initialize();
                rootNode.initializeRoot(leftPid, keyToInsert, pidToInsert);
                
                rootPid = pf.endPid();
                treeHeight = treeHeight + 1;
                rootNode.write(rootPid, pf);
                
            }    
        }
    }

    
    // Debug:
//    print_node();
//    printf("\n\n");
    
    return 0;
    
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
    
    RC status;
    int currentHeight = 1;
    BTLeafNode leaf;
    PageId currentPid = rootPid;
    
    // go through the middle nodes of the tree
    while(currentHeight < treeHeight){
        BTNonLeafNode nonleaf;
        
        // read data into buffer
        status = nonleaf.read(currentPid, pf);
        if(status != 0)
            return status;
        
        // retrieve the childnode
        status = nonleaf.locateChildPtr(searchKey, currentPid);
        if(status !=0)
            return status;
        
        currentHeight ++;        
    }
    
    // now the currentPid should be pointing at leaf node
    status = leaf.read(currentPid, pf);  //read data into buffer
    if(status != 0)
        return status;
    
    // search key
    int eid;
    status = leaf.locate(searchKey, eid);
    if(status != 0)
        return status;
    
    cursor.pid = currentPid;
    cursor.eid = eid;
    
    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
  PageId pid = cursor.pid;
  int eid = cursor.eid;
  BTLeafNode leaf;
    
  // read the data at pid from page file to leafnode buffer
  RC status = leaf.read(pid, pf);
  if(status != 0)
    return status;
    
  // read the entry from the buffer
  status = leaf.readEntry(eid, key, rid);
  if(status != 0)
    return status;
    
  // next entry, update eid and check if it is valid
  eid = eid + 1;
  if(eid >= leaf.getKeyCount()){
    cursor.eid = 0;
    cursor.pid = leaf.getNextNodePtr();
  }
  else{
    cursor.eid = eid;
  }
  return 0;
}


/*
// for debug purpose
RC BTreeIndex::print_node()
{
    BTLeafNode debug;
    PageId bug_pid = 1;
    int currentHeight = 1;
    queue<PageId> parents;
    parents.push(rootPid);
    
    while(currentHeight < treeHeight){
        BTNonLeafNode midnode;
        PageId midPid = (PageId) parents.front();
        parents.pop();
        if(midPid == 1){
            currentHeight = treeHeight;
            break;
        }        
        midnode.read(midPid, pf);
        for(int i = 0; i <= midnode.getKeyCount(); i++){
            PageId pid;
            midnode.getPageId(i, pid);
            parents.push(pid);
        }
        printf("Traverse PID = %d\n", midPid);
        midnode.print();
    }        
        
    if(currentHeight == treeHeight){
        while(bug_pid != -1){
            debug.read(bug_pid, pf);
            printf("Traverse PID = %d\n", bug_pid);
            for(int i = 0; i < debug.getKeyCount(); i++){
                int k;
                RecordId r;
                debug.readEntry(i, k,r);
                printf("%d, ", k);
            }
            printf("total = %d\n", debug.getKeyCount());
            bug_pid = debug.getNextNodePtr();
        }
    }
}
 */
